package com.cfw.collection;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.cfw.collection.MapTree;

public class TreeSearch {
	private static final Logger logger = LoggerFactory.getLogger(TreeSearch.class);
	
	/**
	 * TreeSearch를 이용한 트리 데이터 조회시 각 노드, 자식노드에 대하여 호출되는 콜백
	 */
	public static abstract class AbstractNavigateCallback {
		
		/**
		 * 소스의 탐색 중에 생성할 전환 복제 타깃 객체
		 */
		private final Object data;
		
		public AbstractNavigateCallback(Object data) { this.data = data; }
		
		public Object getData() { return data; }
		
		/**
		 * 소스의 루트객체에 대한 처리가 구현될 함수, 소스의 탐색노드는 새로운 객체를 생성 반환해야 하나,
		 * 루트객체는 data 멤버에 값을 지정하는 프로세스만 구현 
		 * @param parent
		 * @param userObject
		 */
		abstract public Object onroot(Object parentObject, Object userObject);
		
		/**
		 * 소스의 탐색 노드인 userObject의 parent에 대한 처리가 구현될 함수
		 * 루트노드일 경우에는 parent가 null임, 반환값은 parent에 child로 형태로 구현될 객체  
		 * @param parent
		 * @param userObject
		 * @return
		 */
		abstract public Object onnode(Object parentObject, Object userObject);
	}
	
	/**
	 * TreeSearch를 이용한 트리 데이터 조회시 각 노드와 자식노드를 이동하기 위하여 호출되는 콜백
	 * @param <T>
	 */
	public static abstract class AbstractSourceCallback {
		/**
		 * 탐색 대상 객체
		 */
		private final Object data;
		
		public AbstractSourceCallback(Object data) { this.data = data; }
		
		public Object getData() { return data; }
		
		abstract public boolean isLeaf(Object node);
		abstract public Object getNextSibling(Object node);
		abstract public Object getUserObject(Object node);
		abstract public Object getFirstChild(Object node);
	}	
	
	abstract static public class AbstractMatchCallback {
		abstract public boolean match(MapTree mapTree);
	}	
	
	public static void navigate(final AbstractSourceCallback sourceCallback, final AbstractNavigateCallback targetCallBack) {
		if (sourceCallback == null || targetCallBack == null) { throw new IllegalArgumentException("Navigate call back can't be null"); }
		
		// 자식노드로 탐색시 현재노드를 스택에 push, 모든 자식노드의 탐색 종료 후 pop
		final Stack<Object> stackSource = new Stack<Object>(); 
		// 소스로부터 탐색된 데이터가 콜백에 의해 가공 저장되는데, 이 데이터에 대한 탐색시 사용될 스택
		final Stack<Object> stackTarget = new Stack<Object>(); 
		// 재탐색되는 노드를 구별하기 위해 노드의 리스트 
		final List<Object> done = new ArrayList<Object>();
		
		Object source = sourceCallback.getData(); // 탐색대상 객체, 탐색시 자식노드로 참조가 재할당된다.
		
		Object target = null;
		
		while (source != null) {
			int old = done.indexOf(source);
			
			if (old == -1) { 
				if (target == null) {
					target = targetCallBack.onroot(targetCallBack.getData(), sourceCallback.getUserObject(source));
				} else {
					target = targetCallBack.onnode(target, sourceCallback.getUserObject(source));
				}
			}
			
			if (old == -1 && !sourceCallback.isLeaf(source)) {
				stackSource.push(source);
				stackTarget.push(target);
				done.add(source);
				source = sourceCallback.getFirstChild(source);
			} else {
				Object sibling = sourceCallback.getNextSibling(source);
				
				if (sibling != null) {
					source = sibling;
					target = stackTarget.peek();
				} else {
					if (stackSource.isEmpty()) {
						source = null;
					} else {
						source = stackSource.pop();
						target = stackTarget.pop();
					}
				}
			}
		}
	}		

}
